package 链表和树.链表.digui;
//Java：排序链表
public class SortList{
    public static void main(String[] args) {
        Solution solution = new SortList().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
//    public class ListNode {
//        int val;
//        ListNode next;
//        ListNode() {}
//        ListNode(int val) { this.val = val; }
//        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
//    }
class Solution {
    public ListNode sortList(ListNode head) {
        //前置判断
        if(head == null || head.next == null){// head.next == null单节点就不能再分了
            return head;
        }
        //找到head2（中间节点），断开head2的前一个节点注意这里有不同
        ListNode head2 = middleNode(head);

        //分治思想
        head = sortList(head);
        head2 = sortList(head2);

        //合并
        return mergeTwoLists(head, head2);
    }

    private ListNode mergeTwoLists(ListNode list, ListNode list2) {
            ListNode dummy = new ListNode();//因为要操作头节点，使用哨兵简化特殊情况的判断和操作
        //新链表的哨兵节点
            ListNode cur = dummy;

            while (list != null && list2 != null){
                if(list.val < list2.val){
                    cur.next = list;
                    list = list.next;
                }else {
                    //相等都行
                    cur.next = list2;
                    list2 = list2.next;
                }
                //注意这里需要更新
                cur = cur.next;
            }
            cur.next = list != null ? list :list2;//拼接剩余链表
        return dummy.next;
    }

    private ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = head;
        while (fast != null && fast.next != null){
            pre = slow;//记录slow的前一个节点
            fast = fast.next.next;
            slow = slow.next;
        }
        pre.next = null;//断开
        return slow;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}